Switching networks based on Frame Relay transmission techniques have seen widespread use and acceptance since the first networks utilizing this technology were established in the early 1990's. Frame Relay messaging employs variable-length packet switching that is particularly well suited for the transmission of bursty data. For example, Frame Relay networks are often used to transmit data from one LAN (Local Area Network) to another LAN over a WAN (Wide Area Network). Other applications of this technology include SNA migration, remote access connections and Internet connectivity.
Any networking device which offers Frame Relay connections must be able to combine several virtual connections on the same bandwidth so that statistical multiplexing gains can be achieved when traffic bursts do not overlap. It is a further requirement of such devices that some network connections will be recognized to receive a better quality of service or class of service than other network connections, such that when network congestion occurs, the data associated with superior class of service connections are transmitted by the device before the data associated with inferior class of service connections. Yet another requirement of such devices is that delays experienced on all network connections during periods of congestion be precisely monitored and controlled.
It has been known to employ various techniques of priority queuing of network frames based on known class of service parameters. For instance, a priority queuing scheme known as exhaustive round robin is often used for congestion management. This known method is problematic in that it offers no control over delays experienced during periods of congestion unless complex connection admission algorithms are employed, for instance real time feedback. This known technique also has poor scalability when greater than two different levels of class of service must be supported.
Another prior art queuing scheme known as time-stamped weighted fair queuing is sometimes used for congestion management applications. This particular method, like the exhaustive round robin priority queuing scheme discussed above, also suffers from offering no control over delays encountered during periods of congestion unless complex connection admission algorithms are employed. Further, this prior art method is disadvantageous in that it may allocate bandwidth to low quality of service connections, even in situations when high quality of service connections are suffering unacceptable transmission delays.
With some of the congestion control mechanisms known in this art, congestion thresholds for priority queues are set in terms of bytes and simply use the queue depth to decide when to discard message frames. While this method may be adequate when a single queue is implemented per connection stream, the mechanism suffers from two problems when applied to multiple priority queues. The first problem is that bandwidth is wasted if a stale message frame is transmitted. This may occur, even with weighted length priority queuing algorithms, if the low priority traffic is sparse. It can then take a long time before the low priority queue fills up enough to get any service, by which time the frame at the head of the low priority queue will be stale. The second problem is that where there is just one queue, there is a direct correspondence between setting a congestion threshold in bytes and the delay. In other words, the delay experienced by a frame when the queue is at a particular threshold is equal to the threshold divided by the stream rate. However, this correspondence is lost when there are several multiple priority queues sharing a bandwidth.
There is therefore a need for a method of multiple priority queuing which ensures that data on network connections which have a superior quality of service are transmitted before data on connections with an inferior quality of service. There is also a need for a method of priority queuing which achieves the foregoing advantage while allowing for the monitoring and control of delays experienced on all network connections.
Accordingly, it is an object of the present invention to provide a method of priority queuing which achieves these requirements and overcomes some of the problems and shortcomings associated with known schemes of priority queuing. This and other objects of the present invention will be made apparent in the detailed description of embodiments of the invention which follows.